import com.sun.javafx.image.BytePixelSetter;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class JZ26 {
    /**
     * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
     *
     * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
     *输入：A = [1,2,3], B = [3,1]
     * 输出：false
     *
     */

    /**
     * 思路
     * 先层序遍历A树，找到A树和B树头节点值相同的节点，
     * 在以该节点为 头节点为层序遍历其子树，同时层序遍历B树，比较各层节点得值，
     * 不相同终止遍历，继续遍历A树剩下节点找与B树头节点相同得值得节点
     * 如果层序遍历B树完成，则是子树，
     *
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        if (A!=null){
            linkedList.add(A);
        }
        if(B==null){
            return  false;
        }

        while (linkedList.size()>0) {
            TreeNode node=linkedList.removeFirst();
            if (node.left!=null){
                linkedList.add(node.left);
            }
            if (node.right!=null){
                linkedList.add(node.right);
            }

            if (node.val==B.val){
                LinkedList<TreeNode> list1 = new LinkedList<>();
                LinkedList<TreeNode> list2 = new LinkedList<>();
                list1.add(node);
                list2.add(B);
                while (list2.size()>0){

                    TreeNode nodeB = list2.removeFirst();
                    TreeNode nodeA = list1.removeFirst();

                    if (nodeB.left!=null&&nodeA.left!=null){
                        if (nodeA.left.val==nodeB.left.val){
                            list1.add(nodeA.left);
                            list2.add(nodeB.left);
                        }else {
                            list2.add(nodeB.left);
                            break;
                        }
                    }else if (nodeB.left!=null){
                        list2.add(nodeB.left);
                        break;
                    }

                    if (nodeB.right!=null&&nodeA.right!=null){
                        if (nodeA.right.val==nodeB.right.val){
                            list1.add(nodeA.right);
                            list2.add(nodeB.right);
                        }else {
                            list2.add(nodeB.right);
                            break;
                        }

                    }else if (nodeB.right!=null){
                        list2.add(nodeB.right);
                        break;
                    }
                }
                if (list2.size()==0){
                    return true;
                }
            }

        }
        return false;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
